In today's computer driven world, the creation and development of efficient and robust software has become an important focus and a commercially lucrative industry. A large majority of our personal and business conduct relies upon creation of effective software. As such, a premium is placed on the development of computer programs that run quickly and smoothly. The creation of any efficiency in programming computer programs can yield numerous competitive advantages. This remains true despite the fact that processor speeds have increased, as well as the memory of computers (random access memory, commonly referred to as “RAM”).
One manner of creating efficiencies that relates to how a computer program performs is through certain software algorithms, which help manage the various data used and accessed by the underlying programs. Commonly categorized as “data containers,” or data structured, these algorithms facilitate data management. Effective data management minimizes the amount of time a computer program spends manipulating RAM, which thus increases the speed and efficiency of the underlying software. With the complexity of today's programs and underlying architecture, data management has become a key consideration when creating new computer programs.
One key consideration in data management is the utilization of effective data containers. Most strongly typed computer languages (software languages readable by both humans and machines), such as C+ or C++ use various types of data containers. The most basic type of data container is the array. In its most basic form, an array is a contiguous section of computer memory (i.e., RAM) reserved for maintaining discrete, constituent elements (a single data member within an array). Such an array can be dynamically populated, yet the maximum number of elements cannot change during execution of the underlying program. Alternatively (and frequently), an array is fixed in size by the software programmer.
Generic containers represent one form of data container well suited to a variety of computer programs written in strongly typed programming languages. Generic containers typically used by programmers of these languages include (but are in no way limited to) vectors, lists, stacks and queues. With a stack form of generic container, elements can be stored or referenced with an array. Stack elements are retrieved in “last-in first-out” (LIFO) order. Put another way, the last element added to the array is the first removed—while the first element placed into the array is the last element removed. These various generic containers can be used for different purposes and different applications within a computer program. Effective use of these will maximize efficient use of data.
Strongly typed computer languages typically bundle libraries that include standardized sets of generic containers. These containers are typically implemented with variables, data structures, and arrays. Such containers differ based upon the underlying operations they provide and also by their performance characteristics. Performance of these generic containers often dramatically affects the performance of the client software.
Of all of the various generic containers, those containers, commonly referred to as “stack” containers, frequently afford a software programmer the most effective mechanism to collect and employ data. In such cases, stacks allow for the best mechanism to retrieve and use elements—through the last in and first out order. The operation of placing an element upon a stack is referred to as a “push,” while removing an element from the stack is called a “pop.”
With the advancement of information technology, computer systems now use multi-tasking operating systems. Moreover, multi-tasking has evolved into “multi-threading,” where a software program executes in multiple, concurrent paths of execution and shares computing resources internally, not merely with other programs. Multi-tasking operating systems often may require programs to use resources.
One primary advantage of multi-tasking is the ability to have concurrency, that is, to perform several tasks at once. Similarly, a multi-threaded computer program has one or more threads whose execution transpires in a shared execution environment. One benefit of concurrency is a reduction in idle time. For instance, when one thread of execution is busy-perhaps it is waiting for one or more events to occur other threads can continue to execute and therefore make more productive use of the computer processor. By eliminating idle time, concurrency leads to an overall increased speed of processing.
One challenge inherent in multi-threaded computer programming is the management of the various threads during key points of execution by one or more processors. Coordination of these various threads when executing a program, in particular at points where data containers are shared by multiple threads is referred to as “synchronization.” Synchronizing one or more threads involves their waiting for a set of conditions to arise, perhaps through processing performed by one or more additional threads or by the host operating system. Data involved in these conditions are safeguarded from conflicting operations through acquisition of a synchronization object—often referred to as a “lock.”
With contemporary computer hardware, operating systems may temporarily interrupt execution of a thread. These interruptions and resumptions occur as part of “scheduling.” Scheduling is performed by the underlying operating system, and controls when various threads are given the opportunity to execute. Note that the software programmer has little or no means of predicting when these interruptions will occur.
Because of the complexities surrounding multi-threaded programming, many computer programmers choose an approach to minimize the complexity of their computer programs (and thus often fail to maximize the performance of the resulting software). This approach includes simply avoiding the use of threads. Another approach is to overuse locks (and thereby increase the idle time of any processors executing the program). Moreover, the uncertainty as to how these various locking mechanisms impact the performance of software—and perhaps lead to software bugs—has caused programmers to seek new techniques that might help address the issue of multi-threaded software performance and complexity.
Although different types of locking mechanisms have been developed in order to help accommodate issues and limitations faced by software developers, a more robust alternative may be desirable in the field of computer programming. Put another way, there may be a desire need in the field of data management for a system that may minimize delays on the part of threads as they process a given data-set by reducing the need for locking.